#pragma once

#include <cstddef>
#include <iterator>
namespace unstd{


template<typename T>
class Node{
public:
	Node(const T& node){
		this->object = node;
		this->nextPtr = NULL;
	}

	~Node(){
		this->object = NULL;
		this->nextPtr = NULL;
	}

	void insertBefore(Node<T>* other)
	{
		other->nextPtr = this;
	}
	void insertAfter(Node<T>* other)
	{
		other->nextPtr = this->nextPtr;
		this->nextPtr = other;
	}

	T object;
	Node<T> *nextPtr;
};

template<typename T>	
class SList_Iterator_Forward_Const
	: public std::iterator<std::forward_iterator_tag, T, std::ptrdiff_t,
		const T*, const T&>{
public:
	

	SList_Iterator_Forward_Const(){}
	SList_Iterator_Forward_Const(const SList_Iterator_Forward_Const & other)
	{
		this->current = other.current;
	}
	SList_Iterator_Forward_Const(Node<T> * start)
	{
		this->current = start;
	}

	SList_Iterator_Forward_Const& operator ++()
	{
		this->current = current->nextPtr;
		return *this;
	}
	SList_Iterator_Forward_Const operator ++(int)
	{
		SList_Iterator_Forward_Const<T> copy = new iterator_category(*this);//SList_Iterator_Forward<T>(*this);
		this->operator++();
		return copy;
	}
	friend bool operator ==(const SList_Iterator_Forward_Const& it1, const SList_Iterator_Forward_Const& it2) 
	{
		return (it1.current == it2.current);
	}
	friend bool operator !=(const SList_Iterator_Forward_Const& it1, const SList_Iterator_Forward_Const& it2) {
		return !(it1.current == it2.current);
	}
	reference operator *(){
		return current->object;
	}


	Node<T> *current;

};
template<typename T>	
class SList_Iterator_Forward
	: public std::iterator<std::forward_iterator_tag, T, std::ptrdiff_t,
		T*, T&>{
	
public:
	

	SList_Iterator_Forward(){}
	SList_Iterator_Forward(const SList_Iterator_Forward & other)
	{
		this->current = other.current;
	}
	SList_Iterator_Forward(Node<T> * start)
	{
		this->current = start;
	}

	SList_Iterator_Forward& operator ++()
	{
		this->current = current->nextPtr;
		return *this;
	}
	iterator_category operator ++(int)
	{
		SList_Iterator_Forward<T> copy = new iterator_category(*this);//SList_Iterator_Forward<T>(*this);
		this->operator++();
		return copy;
	}
	friend bool operator ==(const SList_Iterator_Forward& it1, const SList_Iterator_Forward& it2) 
	{
		return (it1.current == it2.current);
	}
	friend bool operator !=(const SList_Iterator_Forward& it1, const SList_Iterator_Forward& it2) {
		return !(it1.current == it2.current);
	}
	reference operator *(){
		return current->object;
	}


	Node<T> *current;
};

template<typename T,class Allocator = std::allocator<T>>
class SList
{

public:

	typedef typename Allocator allocator_type;
	typedef typename T value_type;
	typedef typename T* pointer;
	typedef typename T& reference;
	typedef typename const T& const_reference;
	typedef typename ptrdiff_t difference_type;
	typedef typename size_t size_type;

	typedef typename Allocator::rebind<Node<value_type> >::other node_allocator;
	
	typedef typename SList_Iterator_Forward<T> iterator;
	typedef typename const SList_Iterator_Forward_Const<T> const_iterator;

	node_allocator NodeAllocator;
	
	Node<value_type> *tail;
	Node<value_type> *head;
	size_type length;
	//CONSTRUCTORS 

	explicit SList(  )
	{
		this->tail = this->head = NULL;
		this->length = 0;
	}
	//explicit SList( const Allocator& alloc = Allocator() )
	//{}

	//explicit SList( size_type count,
 //              const T& value = T(),
 //              const Allocator& alloc = Allocator())
	//{}
	SList( const SList& other ){}	
	template <class InputIterator> 
	SList( InputIterator first, InputIterator last, const Allocator& alloc = Allocator() ){}
	

	//DESTRUCTORS
	~SList(){}

	/*----- OPERATORS -------*/
	SList& operator =(const SList& other);
	

	void assign( size_type count, const T& value );
	template< class InputIterator > void assign( InputIterator first, InputIterator last );

	allocator_type get_allocator() const;
	
	/*----- ELEMENT ACCESS -------*/
	reference front(){
		return this->head->object;
	}
	const_reference front() const
	{
		const_reference ref = front();
		return ref;
	}

	reference back();	
	const_reference back() const;

	/*----- ITERATORS -------*/
	iterator begin(){
		return iterator(this->head);
	}
	
	const_iterator begin() const
	{
		return const_iterator(this->head);
	}
	iterator end(){
		return NULL; 	
	}
	const_iterator end() const
	{
		return NULL;
	}


	/*------- CAPACITY ----------*/
	bool empty() const
	{
		return this->length == 0 ? true: false;
	}
	size_type size() const
	{
		return this->length;
	}
	size_type max_size() const;

	/*------- MODIFIERS ----------*/
	void clear(){
		iterator first = begin();
		while(begin != end()){
			begin = erase(beg)
		}
	}
	
	iterator insert( iterator pos, const T& value )
	{
		iterator first = begin();
		iterator prev;
		
		if (pos == begin()){
			push_front(value);
			return begin();
		}
		if (pos.current == end()){
			push_back(value);
			return iterator(this->tail);
		}

		while(first != pos   ){
			if (first == end())
				return end();
			prev = first;
			++first;
		}
		Node<value_type> *n = NodeAllocator.allocate(1);
		NodeAllocator.construct(n, value);
	
		prev.current->nextPtr = n;
		n->nextPtr = first.current;

		++this->length;
		return iterator(n);

	}
	void insert( iterator pos, size_type count, const T& value )
	{
		
		for (int i = 0 ; i < count; ++i){
			pos = insert(pos, value);	
		} 
	}
	//TODO: test
	template <class InputIterator>
	void insert( iterator pos, InputIterator first, InputIterator last)
	{
		while(first != last){
			pos = insert(pos, *first);
			++first;
		}
	}

	iterator erase( iterator pos )
	{
		iterator prev = end();
		iterator curr = this->begin();

		if (pos == begin()){
			pop_front();
			return begin();
		}else if(pos.current == this->tail)
		{
			pop_back();
			return end();
		}
		while(curr != pos ){
			if (curr == end())//not found 
				return end();
			prev = curr;
			++curr;
		}
		iterator next = curr;
		++next;
		--this->length;

		NodeAllocator.destroy(curr.current);
		NodeAllocator.deallocate(curr.current, 1);

		if (this->length == 0){
			this->head = this->tail = NULL;
			return end();
		}
		prev.current->nextPtr= next.current;

		return iterator(next.current);
	}
	iterator erase( iterator first, iterator last )
	{
		while(first != last && first != end()){
			first = erase(first);
		}
		if (first != end()){
			iterator next = first;
			++next;
			erase(first);
			return iterator(next);
		}
		return end();
	}

	void push_back( const T& value )
	{
		
		Node<value_type> *n = NodeAllocator.allocate(1);
		NodeAllocator.construct(n, value);
		if (this->length == 0)
		{
			this->head = this->tail = n ;	
		}else{
			this->tail->nextPtr = n;
			this->tail = n;
		}
		
		
		this->length += 1;
	}

	
	void pop_back(){
		Node<value_type> *toDelete = tail;
		iterator prev = prevNode(iterator(tail));

		--this->length; 
		
		NodeAllocator.destroy(toDelete);
		NodeAllocator.deallocate(toDelete, 1);

		this->tail = prev.current; 
		this->tail->nextPtr = NULL;

	}
	void push_front( const T& value ){
		Node<value_type> *n = NodeAllocator.allocate(1);
		NodeAllocator.construct(n, value);
		
		if (this->length == 0)
		{
			this->head = this->tail = n ;	
		}else{
		
			n->nextPtr = head;
			head = n;
		}
		++this->length;
	}
	
	void pop_front()
	{

		Node<value_type> *toDelete = head;
		this->head = this->head->nextPtr;
		--this->length; 
		
		NodeAllocator.destroy(toDelete);
		NodeAllocator.deallocate(toDelete, 1);

	}
	
	
	//TODO: TEST // non bisogna che value sia costruito usando l'allocator??
	void resize( size_type size, T value = T() )
	{
		if (size < this->size()){
			int diff = this->size() - size;

			for (int i = 0 ; i < diff; ++i){
				pop_back();
			}
		}else if (size > this->size())
		{
			int diff =  size - this->size();

			for (int i = 0 ; i < diff; ++i){
				push_back(value);
			}
		}
	}

	//TODO: test
	void n( SList& other ){
		std::swap(this->NodeAllocator,	other.NodeAllocator);
		std::swap(this->head,other.head);
		std::swap(this->tail,other.tail);
		std::swap(this->length,other.length);

	}
private:

	iterator prevNode(iterator node){
		if (this->length <=1 )
			return end();

		iterator curr = begin();
		iterator prev;
		while(curr != node ){
			if (curr == end())//not found 
				return end();
			prev = curr;
			++curr;
		}
		
		return prev;
	}
	
};

	
}